\relax 
\citation{Scarf_Karlin58}
\citation{bresina02}
\citation{Scarf_Karlin58}
\citation{reservoir}
\citation{feng04,li05}
\citation{lqgc}
\@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{1}}
\newlabel{Introduction}{{1}{1}}
\citation{Scarf_Karlin58}
\citation{bitran,wusd10}
\newlabel{eq:trans_inv}{{1}{2}}
\citation{Scarf_Karlin58}
\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces \relax \fontsize  {9}{11}\selectfont  \abovedisplayskip 8\p@ plus2\p@ minus4\p@ \abovedisplayshortskip \z@ plus\p@ \belowdisplayshortskip 4\p@ plus2\p@ minus2\p@ \def \leftmargin \leftmargini \parsep 4.5\p@ plus2\p@ minus\p@ \topsep 9\p@ plus3\p@ minus5\p@ \itemsep 4.5\p@ plus2\p@ minus\p@ {\leftmargin \leftmargini \topsep 4\p@ plus2\p@ minus2\p@ \parsep 2\p@ plus\p@ minus\p@ \itemsep \parsep }\belowdisplayskip \abovedisplayskip Optimal value function $V^2(x)$ for the CAIC problem represented as an extended algebraic decision diagram (XADD). Here the solid lines represent the $\mathit  {true}$ branch for the decision and the dashed lines the $\mathit  {false}$ branch. To evaluate $V^2(x)$ for any state $x$, one simply traverses the diagram in a decision-tree like fashion until a leaf is reached where the non-parenthetical expression provides the \emph  {optimal value} and the parenthetical expression provides the \emph  {optimal policy} ($a = \pi ^{*,2}(x)$) to achieve value $V^2(x)$.}}{3}}
\newlabel{fig:inv_policy}{{1}{3}}
\newlabel{rew_inv}{{2}{3}}
\newlabel{eq:vfun_inv}{{3}{3}}
\citation{fomdp}
\citation{bahar93add}
\citation{spudd}
\citation{li05}
\@writefile{toc}{\contentsline {section}{\numberline {2}Discrete and Continuous State and Action MDPs (DCMDPs)}{4}}
\citation{boutilier99dt}
\citation{dbn}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.1}Factored Representation}{5}}
\newlabel{sec:dcmdps}{{2.1}{5}}
\newlabel{eq:vfun_def}{{4}{5}}
\citation{feng04,hao09}
\citation{feng04,li05,hao09}
\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces \relax \fontsize  {9}{11}\selectfont  \abovedisplayskip 8\p@ plus2\p@ minus4\p@ \abovedisplayshortskip \z@ plus\p@ \belowdisplayshortskip 4\p@ plus2\p@ minus2\p@ \def \leftmargin \leftmargini \parsep 4.5\p@ plus2\p@ minus\p@ \topsep 9\p@ plus3\p@ minus5\p@ \itemsep 4.5\p@ plus2\p@ minus\p@ {\leftmargin \leftmargini \topsep 4\p@ plus2\p@ minus2\p@ \parsep 2\p@ plus\p@ minus\p@ \itemsep \parsep }\belowdisplayskip \abovedisplayskip Dynamic bayes network (DBN) structure representing the transition and reward function (Left); Transition probabilities in terms of CPF and PLE for the state variables and the reward function in the example(Right). }}{6}}
\newlabel{fig:dbn}{{2}{6}}
\citation{bellman}
\newlabel{rew:nonlinear}{{5}{7}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.2}Solution methods}{7}}
\newlabel{sec:soln}{{2.2}{7}}
\newlabel{eq:qfun}{{6}{7}}
\newlabel{eq:vfun}{{7}{7}}
\citation{fomdp}
\citation{fomdp}
\@writefile{toc}{\contentsline {section}{\numberline {3}Symbolic Dynamic Programming}{8}}
\newlabel{SDP}{{3}{8}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.1}Case Representation and Operations}{8}}
\newlabel{eq:gen_int}{{8}{10}}
\newlabel{eq:casemax_max}{{9}{11}}
\newlabel{alg:vi}{{1}{13}}
\@writefile{loa}{\contentsline {algocf}{\numberline {1}{\ignorespaces \relax \fontsize  {9}{11}\selectfont  \abovedisplayskip 8\p@ plus2\p@ minus4\p@ \abovedisplayshortskip \z@ plus\p@ \belowdisplayshortskip 4\p@ plus2\p@ minus2\p@ \def \leftmargin \leftmargini \parsep 4.5\p@ plus2\p@ minus\p@ \topsep 9\p@ plus3\p@ minus5\p@ \itemsep 4.5\p@ plus2\p@ minus\p@ {\leftmargin \leftmargini \topsep 4\p@ plus2\p@ minus2\p@ \parsep 2\p@ plus\p@ minus\p@ \itemsep \parsep }\belowdisplayskip \abovedisplayskip \texttt  {VI}(CSA-MDP, $H$) $\DOTSB \relbar \joinrel \rightarrow $ $(V^h,\pi ^{*,h})$ }}{13}}
\newlabel{alg:regress}{{2}{13}}
\@writefile{loa}{\contentsline {algocf}{\numberline {2}{\ignorespaces \relax \fontsize  {9}{11}\selectfont  \abovedisplayskip 8\p@ plus2\p@ minus4\p@ \abovedisplayshortskip \z@ plus\p@ \belowdisplayshortskip 4\p@ plus2\p@ minus2\p@ \def \leftmargin \leftmargini \parsep 4.5\p@ plus2\p@ minus\p@ \topsep 9\p@ plus3\p@ minus5\p@ \itemsep 4.5\p@ plus2\p@ minus\p@ {\leftmargin \leftmargini \topsep 4\p@ plus2\p@ minus2\p@ \parsep 2\p@ plus\p@ minus\p@ \itemsep \parsep }\belowdisplayskip \abovedisplayskip \texttt  {Regress}($V,a,\mathaccentV {vec}17E{y}$) $\DOTSB \relbar \joinrel \rightarrow $ $Q$ }}{13}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.2}Symbolic Dynamic Programming (SDP)}{13}}
\newlabel{eq:cond_sub}{{10}{14}}
\newlabel{alg:contMax}{{3}{15}}
\@writefile{loa}{\contentsline {algocf}{\numberline {3}{\ignorespaces \relax \fontsize  {9}{11}\selectfont  \abovedisplayskip 8\p@ plus2\p@ minus4\p@ \abovedisplayshortskip \z@ plus\p@ \belowdisplayshortskip 4\p@ plus2\p@ minus2\p@ \def \leftmargin \leftmargini \parsep 4.5\p@ plus2\p@ minus\p@ \topsep 9\p@ plus3\p@ minus5\p@ \itemsep 4.5\p@ plus2\p@ minus\p@ {\leftmargin \leftmargini \topsep 4\p@ plus2\p@ minus2\p@ \parsep 2\p@ plus\p@ minus\p@ \itemsep \parsep }\belowdisplayskip \abovedisplayskip \texttt  {Continuous Maximization}($y$, $f(\mathaccentV {vec}17E{b},\mathaccentV {vec}17E{x},y)$) $\DOTSB \relbar \joinrel \rightarrow (max_{y}f(\mathaccentV {vec}17E{b},\mathaccentV {vec}17E{x},y))$ }}{15}}
\citation{spudd}
\citation{bahar93add}
\citation{bryant}
\citation{bout96}
\citation{bahar93add}
\citation{spuddip}
\@writefile{toc}{\contentsline {section}{\numberline {4}Extended Algebric Decision Diagrams (XADDs)}{17}}
\newlabel{XADD}{{4}{17}}
\@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces \relax \fontsize  {9}{11}\selectfont  \abovedisplayskip 8\p@ plus2\p@ minus4\p@ \abovedisplayshortskip \z@ plus\p@ \belowdisplayshortskip 4\p@ plus2\p@ minus2\p@ \def \leftmargin \leftmargini \parsep 4.5\p@ plus2\p@ minus\p@ \topsep 9\p@ plus3\p@ minus5\p@ \itemsep 4.5\p@ plus2\p@ minus\p@ {\leftmargin \leftmargini \topsep 4\p@ plus2\p@ minus2\p@ \parsep 2\p@ plus\p@ minus\p@ \itemsep \parsep }\belowdisplayskip \abovedisplayskip Comparison of the three decision diagrams: Binary decision diagrams (BDDs) with boolean leaves and decisions (Left) representing $f(x_1,x_2) = x_1\mathaccentV {bar}016{x_2}+\mathaccentV {bar}016{x_1}$ as shown in the truth table; Algebraic decision diagrams (ADDs) with boolean decision nodes and real values at the leaves (Middle) represented by the truth table; Extended algebraic decision diagrams (XADDs) with polynomial leaves and decision nodes (Right) demonstrating the reward function (\nobreakspace  {}2\hbox {}) for a 12-item stochastic CAIC problem.}}{18}}
\newlabel{fig:bdd_add_xadd}{{3}{18}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.1}Formal Definition and Operations}{18}}
\citation{bryant}
\@writefile{lof}{\contentsline {figure}{\numberline {4}{\ignorespaces \relax \fontsize  {9}{11}\selectfont  \abovedisplayskip 8\p@ plus2\p@ minus4\p@ \abovedisplayshortskip \z@ plus\p@ \belowdisplayshortskip 4\p@ plus2\p@ minus2\p@ \def \leftmargin \leftmargini \parsep 4.5\p@ plus2\p@ minus\p@ \topsep 9\p@ plus3\p@ minus5\p@ \itemsep 4.5\p@ plus2\p@ minus\p@ {\leftmargin \leftmargini \topsep 4\p@ plus2\p@ minus2\p@ \parsep 2\p@ plus\p@ minus\p@ \itemsep \parsep }\belowdisplayskip \abovedisplayskip (a) Path and formula definitions on each node in the XADD. A path is defined as a sequence of the tuple $(F^{var},\mathit  {dec})$ and a formula is a set of paths (e.g. $6= (1 \wedge -2)\vee (-1 \wedge -3 \wedge -4)$) (b) Pruning inconsistent nodes of (a) using an LP-Solver which recognizes parent-child relations ($(x \geq -8) \Rightarrow (x \geq -10) $) (c) Pruning redundant nodes of (b) using the SAT-Solver ($(x \leq -12) \Rightarrow (x \geq -8) $).}}{20}}
\newlabel{fig:path_formula}{{4}{20}}
\newlabel{inconsist}{{12}{20}}
\newlabel{redundant}{{13}{20}}
\citation{cox}
\newlabel{algReduceXADD}{{4}{23}}
\@writefile{loa}{\contentsline {algocf}{\numberline {4}{\ignorespaces {\sc  ReduceXADD}(F) }}{23}}
\newlabel{algGetNode}{{5}{23}}
\@writefile{loa}{\contentsline {algocf}{\numberline {5}{\ignorespaces {\sc  GetNode}($\delimiter "426830A \mathit  {var}, F_h, F_l \delimiter "526930B $) }}{23}}
\newlabel{algPrune}{{6}{24}}
\@writefile{loa}{\contentsline {algocf}{\numberline {6}{\ignorespaces {\sc  PruneInconsistent}(F,$\mathit  {decLabel}, \mathit  {decision}$) }}{24}}
\newlabel{algRedundant}{{7}{25}}
\@writefile{loa}{\contentsline {algocf}{\numberline {7}{\ignorespaces {\sc  PruneRedundancy}(X,KB,F) }}{25}}
\newlabel{alg:reorder}{{8}{26}}
\@writefile{loa}{\contentsline {algocf}{\numberline {8}{\ignorespaces {\sc  Reorder}(F) }}{26}}
\@writefile{toc}{\contentsline {subsection}{\numberline {4.2}XADD algorithms and operations}{26}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.2.1}Unary XADD Operations}{26}}
\@writefile{lof}{\contentsline {figure}{\numberline {5}{\ignorespaces \relax \fontsize  {9}{11}\selectfont  \abovedisplayskip 8\p@ plus2\p@ minus4\p@ \abovedisplayshortskip \z@ plus\p@ \belowdisplayshortskip 4\p@ plus2\p@ minus2\p@ \def \leftmargin \leftmargini \parsep 4.5\p@ plus2\p@ minus\p@ \topsep 9\p@ plus3\p@ minus5\p@ \itemsep 4.5\p@ plus2\p@ minus\p@ {\leftmargin \leftmargini \topsep 4\p@ plus2\p@ minus2\p@ \parsep 2\p@ plus\p@ minus\p@ \itemsep \parsep }\belowdisplayskip \abovedisplayskip Representing one step of Continuous Maximization algorithm using XADDs. (a) The upper and lower bounds of action $a$ represented by XADDs (b) substituted inside the leaf node $-75 + 0.1*x - 0.3 * a$ (c) The maximum of the upper and lower bound substitutions (d) considering the constraints (LB< UB) and independent decisions (e) Total maximum considering (-Infinity) as the lower bound.}}{27}}
\newlabel{fig:xadd_max}{{5}{27}}
\newlabel{algLinearize}{{9}{28}}
\@writefile{loa}{\contentsline {algocf}{\numberline {9}{\ignorespaces {\sc  ReduceLinearize}(F) }}{28}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.2.2}Binary XADD Operations}{28}}
\newlabel{algChooseVarBranch}{{10}{29}}
\@writefile{loa}{\contentsline {algocf}{\numberline {10}{\ignorespaces {\sc  ChooseVarBranch}($F_1,F_2$) }}{29}}
\@writefile{lot}{\contentsline {table}{\numberline {1}{\ignorespaces Input case and result for the method \emph  {ComputeResult} for binary operations $\oplus $, $\ominus $ and $\otimes $ for XADDs.}}{29}}
\newlabel{tab:ComputeResultXADD}{{1}{29}}
\newlabel{algApply}{{11}{30}}
\@writefile{loa}{\contentsline {algocf}{\numberline {11}{\ignorespaces {\sc  Apply}($F_1,F_2,\mathit  {op}$) }}{30}}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {4.2.3}Apply Algorithm for binary operations of XADDs}{30}}
\@writefile{toc}{\contentsline {section}{\numberline {5}Experimental Results}{31}}
\newlabel{results}{{5}{31}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.1}Domains}{31}}
\@writefile{toc}{\contentsline {paragraph}{\textsc  {Knapsack}}{31}}
\@writefile{toc}{\contentsline {paragraph}{\textsc  {Mars Rover }}{32}}
\newlabel{trans:nonlin}{{14}{33}}
\newlabel{rew:nonlin}{{15}{33}}
\@writefile{lof}{\contentsline {figure}{\numberline {6}{\ignorespaces \relax \fontsize  {9}{11}\selectfont  \abovedisplayskip 8\p@ plus2\p@ minus4\p@ \abovedisplayshortskip \z@ plus\p@ \belowdisplayshortskip 4\p@ plus2\p@ minus2\p@ \def \leftmargin \leftmargini \parsep 4.5\p@ plus2\p@ minus\p@ \topsep 9\p@ plus3\p@ minus5\p@ \itemsep 4.5\p@ plus2\p@ minus\p@ {\leftmargin \leftmargini \topsep 4\p@ plus2\p@ minus2\p@ \parsep 2\p@ plus\p@ minus\p@ \itemsep \parsep }\belowdisplayskip \abovedisplayskip Optimal sum of rewards (value) $V^t(x)$ for $b = 0 \tmspace  +\thinmuskip {.1667em} (\mathit  {false})$ for time horizons (i.e., decision stages remaining) $t=0$, $t=1$, and $t=2$ on the \textsc  {Continuous Action} \textsc  {Mars Rover }\ problem. For $x \in [-2,2]$, the rover automatically takes a picture and receives a reward quadratic in $x$. We initialized $V^0(x,b) = R(x,b)$; for $V^1(x)$, the rover achieves non-zero value up to $x = \pm 12$ and for $V^2(x)$, up to $x = \pm 22$.}}{34}}
\newlabel{fig:opt_graph}{{6}{34}}
\@writefile{lof}{\contentsline {figure}{\numberline {7}{\ignorespaces \relax \fontsize  {9}{11}\selectfont  \abovedisplayskip 8\p@ plus2\p@ minus4\p@ \abovedisplayshortskip \z@ plus\p@ \belowdisplayshortskip 4\p@ plus2\p@ minus2\p@ \def \leftmargin \leftmargini \parsep 4.5\p@ plus2\p@ minus\p@ \topsep 9\p@ plus3\p@ minus5\p@ \itemsep 4.5\p@ plus2\p@ minus\p@ {\leftmargin \leftmargini \topsep 4\p@ plus2\p@ minus2\p@ \parsep 2\p@ plus\p@ minus\p@ \itemsep \parsep }\belowdisplayskip \abovedisplayskip Optimal value function $V^1(x)$ for the \textsc  {Continuous Action} \textsc  {Mars Rover }\ problem represented as an extended algebraic decision diagram (XADD). Here the solid lines represent the $\mathit  {true}$ branch for the decision and the dashed lines the $\mathit  {false}$ branch. To evaluate $V^1(x)$ for any state $x$, one simply traverses the diagram in a decision-tree like fashion until a leaf is reached where the non-parenthetical expression provides the \emph  {optimal value} and the parenthetical expression provides the \emph  {optimal policy} ($y = \pi ^{*,1}(x)$) to achieve value $V^1(x)$.}}{34}}
\newlabel{fig:opt_val_pol}{{7}{34}}
\citation{Mahootchi2009,Yeh1985}
\@writefile{toc}{\contentsline {paragraph}{\textsc  {Reservoir Management }}{35}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.2}Results}{35}}
\@writefile{lof}{\contentsline {figure}{\numberline {8}{\ignorespaces Space (\# XADD nodes in value function) and time to optimally solve different problem sizes of the two \textsc  {Discrete Action} \textsc  {Mars Rover }\nobreakspace  {}domains for varying horizon lengths.}}{36}}
\newlabel{fig:all_lin}{{8}{36}}
\@writefile{lof}{\contentsline {figure}{\numberline {9}{\ignorespaces Space (\# XADD nodes in value function) and time for different iterations (horizons) of SDP on \textsc  {Discrete Action} \textsc  {Mars Rover Linear }\ with 3 image target points. Results shown for SDP with and without XADD infeasible path pruning.}}{37}}
\newlabel{fig:lin3}{{9}{37}}
\@writefile{lof}{\contentsline {figure}{\numberline {10}{\ignorespaces \emph  {Optimal} value function (vertical axis) for different domains showing \emph  {non-rectangular} piecewise boundaries. From left to right, \textsc  {Knapsack}\ ($H = \infty $, horizontal axes $x_2$ and $x_1$), \textsc  {Mars Rover Linear }\ with two pictures ($H = 8$, horizontal axes $\mathit  {energy}$ and $\mathit  {time}$), and \textsc  {Mars Rover Nonlinear }\ with one picture ($H = 3$, horizontal axes $y$ and $x$).}}{37}}
\newlabel{fig:plot3D}{{10}{37}}
\@writefile{lof}{\contentsline {figure}{\numberline {11}{\ignorespaces Space (\# XADD nodes in value function) and time for different iterations (horizons) of SDP on Nonlinear \textsc  {Continuous Action} \textsc  {Mars Rover }\ with 3 different results based on pruning techniques. Results are shown for the XADD with no pruning technique, with only inconsistency checking (using LP-solver) and with both the inconsistent and redundancy checking (using LP-Solver and SAT-Solver).}}{38}}
\newlabel{fig:roverTS}{{11}{38}}
\@writefile{lof}{\contentsline {figure}{\numberline {12}{\ignorespaces Reservoir Management: space and elapsed time vs. horizon. Comparing the two algorithms for inconsistency pruning (IPrune) and redundancy and inconsistency pruning (RIPrune). }}{38}}
\newlabel{fig:resTimeSpace}{{12}{38}}
\citation{feng04}
\citation{li05}
\citation{hao09}
\citation{feng04}
\citation{penberthy94}
\@writefile{lof}{\contentsline {figure}{\numberline {13}{\ignorespaces \textsc  {Reservoir Management }: {\it  (left)} Policy $\mathit  {no}$-$\mathit  {drain}(e)=\pi ^{2,*}(l_1,l_2)$ showing on the z-axis the elapsed time $e$ that should be executed for $\mathit  {no}$-$\mathit  {drain}$ conditioned on the states; {\it  (middle)} $V^2(l_1,l_2)$; {\it  (right)} $V^9(l_1,l_2)$. }}{39}}
\newlabel{fig:v2plots}{{13}{39}}
\@writefile{lof}{\contentsline {figure}{\numberline {14}{\ignorespaces \textsc  {Inventory Control }: space and time vs. horizon. }}{39}}
\newlabel{fig:invC}{{14}{39}}
\@writefile{toc}{\contentsline {section}{\numberline {6}Related Work}{39}}
\citation{boyan01}
\citation{phase07}
\citation{kveton06}
\citation{munos02}
\citation{lqgc}
\citation{hao09}
\citation{apricodd}
\citation{munos02,kveton06,phase07}
\@writefile{toc}{\contentsline {section}{\numberline {7}Concluding Remarks}{40}}
\citation{hao09}
\citation{li05}
\citation{apricodd}
\bibdata{exactsdp}
\bibstyle{theapa}
